// https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/submissions/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

// 这个函数的功能有三个：给定两个节点 p 和 q
// 如果 p 和 q 都存在，则返回它们的公共祖先；
// 如果只存在一个，则返回存在的一个；
// 如果 p 和 q 都不存在，则返回 NULL
// 本题说给定的两个节点都存在，那自然还是能用该函数来解决

class Solution {
public:
    // 法一：DFS 转换为root往下能否找到p节点或q节点；确保肯定能找到，并且DFS返回的是最接近的
    // https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/er-cha-shu-de-zui-jin-gong-gong-zu-xian-by-leetc-2/ 无明逆流的回答
    // TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    //     if (!root) return NULL;
    //     if (root == p || root == q) return root; // 注意！
    //     TreeNode* left = lowestCommonAncestor(root->left, p, q);
    //     TreeNode* right = lowestCommonAncestor(root->right, p, q);
    //     if (left && right) return root;
    //     // 肯定能找到，所以一个为NULL另一个就包含两个
    //     if (left) return left; 
    //     return right;
    // }

    // 法二：存储父节点
    unordered_map<TreeNode*, TreeNode*> fa;
    unordered_map<TreeNode*, bool> rec;
    void helper(TreeNode* root) {
        if (root->left) {
            fa[root->left] = root;
            helper(root->left);
        }
        if (root->right) {
            fa[root->right] = root;
            helper(root->right);
        }
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        fa[root] = NULL;
        helper(root);
        while (p) {
            rec[p] = true;
            p = fa[p];
        }
        while (q) {
            if (rec[q]) return q;
            q = fa[q];
        }
        return NULL;
    }
};